class Node:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None
        self.count = 1


class AllOne(object):

    def __init__(self):
        self.big = None
        self.small = None
        self.d = {}

    def inc(self, key):
        """
        :type key: str
        :rtype: None
        """
        if not self.big:
            node = Node(key)
            self.big = node
            self.small = node
            self.d[key] = node
        else:
            if key in self.d:
                node = self.d[key]
                node.count += 1
                while node.prev and node.prev.count < node.count:
                    prev_node = node.prev
                    next_node = node.next
                    prev_node.next = next_node
                    if next_node:
                        next_node.prev = prev_node
                    else:
                        self.small = prev_node
                    node.next = prev_node
                    node.prev = prev_node.prev
                    if prev_node.prev:
                        prev_node.prev.next = node
                    prev_node.prev = node
                if not node.prev:
                    self.big = node
            else:
                node = Node(key)
                self.d[key] = node
                node.prev = self.small
                self.small.next = node
                self.small = node



    def dec(self, key):
        """
        :type key: str
        :rtype: None
        """
        node = self.d[key]
        node.count -= 1
        if node.count == 0:
            self.d.pop(key)
            if node.prev:
                prev_node = node.prev
                if node.next:
                    next_node = node.next
                    prev_node.next = next_node
                    next_node.prev = prev_node
                else:
                    prev_node.next = None
                    self.small = prev_node
            else:
                if node.next:
                    next_node = node.next
                    next_node.prev = None
                    self.big = next_node
                else:
                    self.big = None
                    self.small = None
        else:
            while node.next and node.next.count > node.count:
                prev_node = node.prev
                next_node = node.next
                next_node.prev = prev_node
                if prev_node:
                    prev_node.next = next_node
                else:
                    self.big = next_node
                node.prev = next_node
                if next_node.next:
                    node.next = next_node.next
                    next_node.next.prev = node
                else:
                    node.next = None
                    self.small = node
                next_node.next = node


    def getMaxKey(self):
        """
        :rtype: str
        """
        if self.big:
            return self.big.val
        else:
            return ''

    def getMinKey(self):
        """
        :rtype: str
        """
        if self.small:
            return self.small.val
        else:
            return ''

obj = AllOne()
obj.inc('a')
obj.inc('b')
obj.inc('b')
obj.inc('c')
obj.inc('c')
obj.inc('c')
obj.inc('c')
print(obj)